package datastructure.book.dp._1_pathway.exercise.first;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _9_Solution {
    /**
     * 给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。
     * 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。
     * 在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
     * 一条路径的 「得分」 定义为：路径上所有数字的和。
     * 请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，
     * 请把结果对 10^9 + 7 取余。
     * 如果没有任何路径可以到达终点，请返回 [0, 0] 。
     * 例：
     * E51
     * 12X
     * 3XS
     * 得分最大路径  S->2->5->E  结果为[7,1]
     * E12
     * 121
     * 21S
     * 结果为[4,6]
     */
    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        char[][] chars = new char[n][n];
        for (int i = 0; i < board.size(); i++) {
            String s = board.get(i);
            chars[i] = s.toCharArray();
        }
        int[][][] dp = new int[n][n][2];
        dp[n-1][n-1][1] = 1;
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                char c = chars[i][j];
                if (c == 'S' || c == 'X') {
                    continue;
                }
                int rightScore = getScore(i,j+1,n,chars,dp);
                int downScore = getScore(i+1,j,n,chars,dp);
                int rightDownScore = getScore(i+1,j+1,n,chars,dp);
                if (rightScore > downScore) {
                    if (rightScore > rightDownScore) {
                        dp[i][j][0] = rightScore+(chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i][j+1][1];
                    } else if (rightScore < rightDownScore) {
                        dp[i][j][0] = rightDownScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i + 1][j + 1][1];
                    } else {
                        dp[i][j][0] = rightScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i][j+1][1] + dp[i + 1][j + 1][1];
                        dp[i][j][1] %= 1000000007;
                    }
                } else if (rightScore < downScore) {
                    if (downScore > rightDownScore) {
                        dp[i][j][0] = downScore+(chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i+1][j][1];
                    } else if (downScore < rightDownScore) {
                        dp[i][j][0] = rightDownScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i + 1][j + 1][1];
                    } else {
                        dp[i][j][0] = downScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i+1][j][1] + dp[i + 1][j + 1][1];
                        dp[i][j][1] %= 1000000007;
                    }
                } else {
                    if (rightScore > rightDownScore) {
                        dp[i][j][0] = rightScore+(chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i+1][j][1]+dp[i][j + 1][1];
                        dp[i][j][1] %= 1000000007;
                    } else if (rightScore < rightDownScore) {
                        dp[i][j][0] = rightDownScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i + 1][j + 1][1];
                    } else if (rightScore != -1) {
                        dp[i][j][0] = downScore + (chars[i][j] == 'E' ? 0:chars[i][j]-'0');
                        dp[i][j][1] = dp[i + 1][j][1] + dp[i + 1][j + 1][1] + dp[i][j + 1][1];
                        dp[i][j][1] %= 1000000007;
                    }
                }
            }
        }
        if (dp[0][0][1] > 0) {
            return new int[]{dp[0][0][0], dp[0][0][1]};
        } else {
            return new int[]{0,0};
        }
    }

    private int getScore(int i, int j, int n, char[][] chars, int[][][] dp) {
        if (i < n && j < n && chars[i][j] != 'X' && dp[i][j][1] > 0) {
            return dp[i][j][0];
        }
        return -1;
    }

    @Test
    public void test(){
        List<String> board = new ArrayList<>();
        board.add("E11");
        board.add("XXX");
        board.add("21S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
        board = new ArrayList<>();
        board.add("E1222X");
        board.add("XXXXX5");
        board.add("211674");
        board.add("312671");
        board.add("312671");
        board.add("31267S");
        System.out.println(Arrays.toString(pathsWithMaxScore(board)));
    }
}
